#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// 多项式哈希
const ll HASH_BASE = 13331;
const ll HASH_BASE2 = 131;
const ll HASH_MOD = 998244353;
const ll HASH_MOD2 = 1e9 + 9;

template <int L>
struct SHash
{
    array<ll, L> mods;
    array<vector<ll>, L> psum;
    array<vector<ll>, L> fact;

    array<size_t, L> operator()(int l, int r) const
    {
        array<size_t, L> ans;
        for (int i = 0; i < L; i++)
        {
            ll res = (psum[i][r] - psum[i][l - 1] * fact[i][r - l + 1] % mods[i]) % mods[i];
            size_t raw = (res + mods[i]) % mods[i];
            ans[i] = splitmix64(raw);
        }

        return ans;
    }

    size_t splitmix64(size_t x) const
    {
        static const size_t fixed = chrono::steady_clock::now().time_since_epoch().count();
        x += 0x9e3779b97f4a7c15 + fixed;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
};

template <int L>
struct SHasher
{
    array<ll, L> _bases, _mods;
    SHasher(array<ll, L> bases, array<ll, L> mods) : _bases(bases), _mods(mods) {}

    // 输入1化字符串
    SHash<L> operator()(const string &str) const
    {
        SHash<L> res;
        res.mods = _mods;

        for (int i = 0; i < L; i++)
        {
            res.fact[i].resize(str.size());
            res.psum[i].resize(str.size());
            res.fact[i][0] = 1;
            for (int j = 1; j < str.size(); j++)
            {
                res.fact[i][j] = res.fact[i][j - 1] * _bases[i] % _mods[i];
                res.psum[i][j] = (res.psum[i][j - 1] * _bases[i] % _mods[i] + str[j]) % _mods[i];
            }
        }
        return res;
    }
};